package leetcode_interview;

/**
 * @author 歪大哥😁
 * @date 2020-07-29.
 * 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
 *
 * 示例 1：
 *
 * 输入: s = "leetcode"
 * 输出: false
 * 示例 2：
 *
 * 输入: s = "abc"
 * 输出: true
 * 限制：
 *
 * 0 <= len(s) <= 100
 * 如果你不使用额外的数据结构，会很加分。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/is-unique-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class N0101 {

    public static void main(String[] args) {
        String s = "aabc";
        System.out.println(isUnique(s));
    }

    static boolean isUnique(String astr) {
        // ascii码一共有127个 通过两个long型数进存储 0表示不存在 1表示存在
        long left = 0L;
        long right = 0L;
        for (int i = 0; i < astr.length(); i++) {
            char c = astr.charAt(i);
            if (c >= 64) {
                // 使用left
                if (isExist(left, c - 64)) {
                    // 字符出现过了
                    return false;
                } else {
                    left = mark(left, c - 64);
                }
            } else {
                // 使用right
                if (isExist(right, c)) {
                    // 字符出现过了
                    return false;
                } else {
                    right = mark(right, c);
                }
            }
        }
        return true;
    }

    static long mark(long oldBox, int index) {
        return oldBox | (1L << index);
    }

    static boolean isExist(long box, int index) {
        return (box & (1L << index)) > 0;
    }

}
